package main

import "fmt"

type Ring struct {
	next, prev *Ring       // 前驱和后驱节点
	Value      interface{} // 数据
}

// 初始化空的循环链表，前驱和后驱都指向自己
// 时间复杂度： O（1）
func (r *Ring) init() *Ring {
	r.next = r
	r.prev = r
	return r
}

// 创建指定大小N的循环链表，值全部是空
// 时间复杂度：O（n）
func New(n int) *Ring {
	if n <= 0 {
		return nil
	}
	r := new(Ring) // 创建节点对象(头节点)
	p := r         // 游标节点
	for i := 0; i < n; i++ {
		p.next = &Ring{prev: p}
		p = p.next
	}
	p.next = r
	r.prev = p
	return r
}

// 获取上一个节点
// 时间复杂度：O（1）
func (r *Ring) Prev() *Ring {
	if r.next == nil { // 边界条件判断
		return r.init()
	}
	return r.prev
}

// 获取下一个节点
// 时间复杂度：O（1）
func (r *Ring) Next() *Ring {
	if r.next == nil {
		return r.init()
	}
	return r.next
}

// 获取第n个节点
// 时间复杂度： O（n）
func (r *Ring) Move(n int) *Ring {
	if r.next == nil {
		return r.init()
	}
	p := r
	switch {
	case n < 0:
		for ; n < 0; n++ {
			p = p.prev
		}
	case n > 0:
		for ; n > 0; n-- {
			p = p.next
		}
	}
	return p
}

// 添加节点
// 往节点r，链接一个节点，并且返回之前节点r的后驱节点
// 时间复杂度：O（n），需要注意，r 和 s 都是环形链表。
func (r *Ring) Link(s *Ring) *Ring {
	n := r.Next()
	if s != nil {
		p := s.Prev()
		r.next = s
		s.prev = r
		p.next = n
		n.prev = p
	}
	return n
}

// 删除指定节点的后续n个节点
// 时间复杂度：O（n）
func (r *Ring) Unlink(n int) *Ring {
	if n < 0 {
		return nil
	}
	return r.Link(r.Move(n + 1))
}

// 获取链表长度
// 时间复杂度：O（n）
func (r *Ring) Len() int {
	n := 0
	if r != nil {
		n = 1
		for p := r.Next(); p != r; p = p.next {
			n++
		}
	}
	return n
}

// test
func linkNewTest() {
	// 第一个节点
	r := &Ring{Value: -1}

	// 链接新的5个节点
	// 头插法的效果
	r.Link(&Ring{Value: 1})
	r.Link(&Ring{Value: 2})
	r.Link(&Ring{Value: 3})
	r.Link(&Ring{Value: 4})

	temp := r.Unlink(3) // 解除了后面3个节点

	node := r

	// 打印原来的节点值
	for {
		// 打印节点值
		fmt.Println(node.Value)

		// 遍历到下一个节点
		node = node.next

		// 判断，如果节点回到起点，结束遍历
		if node == r {
			break
		}
	}

	fmt.Println("===========")

	// 打印被切断的节点值
	node = temp
	for {
		//  打印节点值
		fmt.Println(node.Value)
		node = node.next

		if node == temp {
			break
		}
	}
}

func main() {
	linkNewTest()
}
